package linkedlist;

import org.junit.Test;

import static linkedlist.ListNode.buildList;

public class IsPalindrome234 {

    @Test
    public void test() {
        ListNode list1 = buildList(1);
        System.out.println(isPalindrome(list1));

        ListNode list2 = buildList(1, 2);
        System.out.println(isPalindrome(list2));

        ListNode list3 = buildList(1, 2, 1);
        System.out.println(isPalindrome(list3));

        ListNode list4 = buildList(1, 2, 2, 1);
        System.out.println(isPalindrome(list4));

        ListNode list5 = buildList(1, 2, 3, 1);
        System.out.println(isPalindrome(list5));
    }

    public boolean isPalindrome(ListNode head) {
        if (head == null) {
            return false;
        }
        if (head.next == null) {
            return true;
        }

        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        // 如果有奇数个节点: fast=最后节点, slow=正中间节点
        // 如果有偶数个节点: fast=null, slow=后半段起始节点

        // 翻转[head, slow.prev]这段节点
        ListNode prev = null;
        ListNode curr = head;
        while (curr != slow) {
            ListNode next = curr.next;
            curr.next = prev;

            prev = curr;
            curr = next;
        }

        //prev成为前半段翻转后的起始节点
        ListNode l1 = prev;
        ListNode l2 = (fast == null) ? slow : slow.next;

        while (l1 != null && l2 != null) {
            if (l1.val != l2.val) {
                return false;
            }
            l1 = l1.next;
            l2 = l2.next;
        }
        return true;
    }

    public boolean isPalindrome1(ListNode head) {
        if (head == null) {
            return false;
        }

        int len = getLength(head);
        ListNode subTailNext = isSubListPalindromeAndReturnSubTail(head, len);
        return subTailNext != null;
    }

    public int getLength(ListNode head) {
        int len = 0;
        while (head != null) {
            len++;
            head = head.next;
        }
        return len;
    }

    /**
     * null indicates the sublist is not palindrome
     */
    public ListNode isSubListPalindromeAndReturnSubTail(ListNode subHead, int subLength) {
        if (subLength == 1) {
            return subHead;
        }
        if (subLength == 2) {
            ListNode subTail = subHead.next;
            if (subTail.val == subHead.val) {
                return subTail;
            } else {
                return null;
            }
        }

        ListNode subTailPrev = isSubListPalindromeAndReturnSubTail(subHead.next, subLength-2);
        if (subTailPrev != null) {
            ListNode subTail = subTailPrev.next;
            if (subHead.val == subTail.val) {
                return subTail;
            }
        }
        return null;
    }
}
